A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion

摘要

We consider the problem of reconstructing a low-rank matrix from a smallsubset of its entries. In this paper, we describe the implementation of anefficient algorithm called OptSpace, based on singular value decompositionfollowed by local manifold optimization, for solving the low-rank matrixcompletion problem. It has been shown that if the number of revealed entries islarge enough, the output of singular value decomposition gives a good estimatefor the original matrix, so that local optimization reconstructs the correctmatrix with high probability. We present numerical results which show that thisalgorithm can reconstruct the low rank matrix exactly from a very small subsetof its entries. We further study the robustness of the algorithm with respectto noise, and its performance on actual collaborative filtering datasets.